1. Field of the Invention
The present invention relates generally to systems and methods for generating solutions to global optimization problems. More particularly, the present invention relates to systems and methods for finding improved solutions to mixed integer problems through the use of evolutionary algorithms.
2. Brief Summary of the Invention
Mixed Integer Programming is a versatile, widely used technique for solving a variety of practical optimization problems. Generally, a mixed integer program (“MIP”) is an optimization problem of the form:                minimize f(x)        subject to G(x)=b                    l≦x≦u                        some or all xj integral,where x is a vector of variables, l and u are vectors of bounds, f(x) is an objective expression, and G(x)=b is a set of constraint expressions. While the above model has a minimization objective, one of skill will recognize that models may have maximization objectives.        
The simplest and most widely used form of MIP model is the Mixed Integer Linear Program (MILP):                minimize cTx        subject to Ax=b                    l≦x≦u                        some or all xj integral,where A is an m by n matrix, called the constraint matrix, and c is the linear objective vector. Thus, as one of ordinary skill in the art would recognize, a MILP is a linear program (“LP”) with an integrality restriction on some or all of the variables. Other forms of MIP model include the Mixed Integer Quadratic Program (MIQP), Mixed Integer Quadratically Constrained Program (MIQCP), and Mixed Integer Non Linear Program (MINLP).        
While the integrality restriction makes MIPs difficult to solve (both in general terms, and NP-hard in the technical sense), this restriction also makes the mixed-integer modeling paradigm a powerful tool in representing real-world business applications. In many situations, the solution to a MIP can yield a cost or benefit (for example, in dollars or other units) of pursuing a certain course of business. In a situation wherein the MIP solution yields a cost in dollars, the optimal solution might be one wherein the dollar cost is minimized. In a situation wherein the MIP solution yields the number of linear-feet of lumber that can be harvested from a forest, the optimal solution might be a solution wherein the number of linear-feet is maximized.
While absolute optimal solutions can and have been found for some MIPs (e.g., some MIPs with a small number of variables (n) or constraints (m)), for many MIPs, only solutions that are not provably optimal have been found. These solutions are often referred to as “best known” or “best objective” solutions. Such best known solutions still provide significant practical value in many situations. In these cases, it is often desirable to find the best known solution using the least amount of resources.
(As used herein, “resources” can refer to money, time (seconds, minutes, hours, days, weeks, etc.), computer processor cycles, man-hours, or any other resource of which further depletion might theoretically yield a better solution. As also used herein, “optimize” means to improve the result, regardless of whether such improvement results in the absolute optimal result.)
For still other MIPs, no solution has yet been found. In such cases, it is necessary to find an initial feasible solution to the MIP model before the teachings set forth herein may be used to improve upon the initial solution while using a limited amount of resources.
More particularly, while with unlimited resources it might be possible to find one or more provably optimal or best objective solutions to any MIP, within the bounds of practicality, available resources are often limited. For example, the MIP solution might yield the distance and roads taken for the shortest road route between Lakeside, Ariz. and New York, N.Y. If this solution is being generated by a business interest, for a person using an internet mapping service, the limiting resource might be a time limitation of ten seconds. If forced to wait longer than ten seconds for a solution, the person might become frustrated and request a solution from a competitor. In this example, it would be desirable to find a best known solution with a resource limitation of ten seconds. However, without the resource limitation, it might be possible to find a provably optimal solution by considering every road leaving Lakeside, Ariz., every connecting road, and so on. Yet, the provably optimal solution might be less valuable if not delivered within the appropriate resource limitation.
In another example, the MIP solution might yield the cost in dollars of deploying each of 10,000 employees, having diverse skill sets, to perform certain tasks for a company. It might be desirable to determine the least costly manner to deploy the employees. Without any resource limitation, it might be possible to find a provably optimal solution by considering every possible deployment of every employee. Yet, the provably optimal solution might be less valuable if not delivered within an appropriate resource limitation. That is, the cost of exceeding the resource limitation might exceed the cost savings realized by finding a provably optimal solution.
Other examples of optimality problems addressed by MIPs include optimization of supply chain configurations (see U.S. Patent Application Publication Serial No. US 2002/0156663 A1, dated Oct. 24, 2002), loading patterns for a nuclear reactor core (see U.S. Patent Application Publication Serial No. US 2004/0196946 A1, dated Oct. 7, 2004), supply channel and contract modeling (see U.S. Patent Application Publication Serial No. US 2004/0172321 A1, dated Sep. 2, 2004), airline scheduling and ticket sales, and many other complex problems.
The standard technique for solving MIP problems is a version of divide-and-conquer known as relaxation-based branch-and-cut. The branch-and-cut algorithm begins by solving the continuous relaxation, obtained by simply deleting the integrality restrictions. If the relaxation is found to be infeasible, then the original problem is also infeasible and the algorithm is complete. If the relaxation has a solution, and the solution satisfies all the integrality restrictions of the problem, the solution is optimal and the algorithm is complete. Otherwise, some integrality restriction is violated. In this case, an integral variable xj having a currently fractional value xj*, is picked. The problem is “branched,” creating two disjoint “child” problems from the initial single “parent” problem by restricting the range of the integral variable. Specifically, a variable with a lower bound l and an upper bound u will be divided into two problems with ranges l to q and q+1 to u, respectively. These two child nodes are subsequently processed, possibly creating further child nodes.
In the course of exploring nodes, the branch-and-cut algorithm maintains bounds on the best and worst possible objective value that may be attained by the optimal solution. Feasible solutions provide bounds on the worst objective value. Bounds on the best objective value are obtained from the continuous relaxations of the problem.
At each node, the branch-and-cut algorithm can optionally search for constraints which are violated by the continuous relaxation, but not violated by any optimal integer solutions. Such constraints are referred to as cutting planes. When these constraints are added, the old non-final solution is no longer valid, and the new solution generated will be different, potentially resulting in a better lower bound for that child problem.
The branch-and-cut algorithm continues processing nodes created in this manner until the set of unprocessed nodes is exhausted, or until a user-imposed resource limit is exceeded.
More recently, methods for finding high quality, feasible solutions to MIP models that involve exploring the neighborhood of a given feasible solution (referred to as “limited neighborhood exploration strategies”), have also been investigated. One such approach is called Relaxation Induced Neighborhood Search (“RINS”). This method constructs a promising neighborhood using information contained in the continuous relaxation of the MIP model. Neighborhood exploration is then formulated as a MIP model itself and solved recursively. Another approach, called guided dives (“GD”), is a simple modification of the MIP tree traversal order. This technique “guides” the search towards nodes that are close neighbors of the best known feasible solution. Further discussion of RINS and GD can be found in Emilie Danna et al., Exploring relaxation induced neighborhoods to improve mip solutions, Mathematical Programming, 98:23-47, 2002. A third such limited neighborhood exploration strategy is local branching (“LB”). LB is a local search meta-heuristic for MIPs that is entirely embedded in a branch-and-cut framework, and which partitions the search tree through local branching cuts. See Matteo Fischetti and Andrea Lodi, Local Branching, Mathematical Programming, 98:23-47, 2002.
However, these local neighborhood exploration strategies suffer from several drawbacks. First, such strategies, because they focus on the neighborhoods of a given feasible solution, often yield solution pools that are lacking in diversity. Second, these local exploration strategies can still leave significant optimality gaps for many important MIP models.
One application that employs non-evolutionary algorithms is the Sabre TRIP crew pairing system. This system is described in an article titled, “Recent Advances in Crew-Pairing Optimization at American Airlines,” by Ranga Anbil et al. In this system, the solution to a set partitioning problem is successively improved by iteratively forcing a random collection of sets into the solution, then solving a smaller set partitioning problem on the remaining sets. However, the method employed by TRIP for choosing the subset of variables to fix is domain dependent, i.e. it is based upon structural information about the crew repair problem that the method is designed to solve, and therefore is not applicable to general MIP models. (Indeed, many evolutionary algorithms require structural information about the problem to be solved above and beyond the information contained in the original MIP formulation). Further, this method only searches for an improved solution based upon a single given known solution. It does not maintain a pool of solutions. Therefore, it ignores sub-optimal solutions that may be useful for improving diversity in a solution pool, and it cannot be integrated within an existing solution generating framework.
In addition to these limited neighborhood exploration strategies, recent attempts at generating solutions to MIPs have also focused on the development of “evolutionary algorithms.” Evolutionary algorithms are based on a natural selection analogy, in which a population of solutions evolves from one generation to the next through combination and mutation. Specifically, evolutionary algorithms typically begin with an initial population of solutions (referred to as a solution pool). While a solution pool may be partially or completely empty, it typically has room for a plurality of solutions. Each of the members of the solution pool is evaluated based on some objective criteria. This evaluation yields an objective value for each member. A subpopulation of the solution pool comprising two or more parents is then selected for offspring production. The parents are combined to generate offspring. The offspring are mutated by introducing random changes into some subset of the offspring. “Survivors” are then selected based upon an evaluation of the mutated offspring using objective criteria, which survivors then constitute a new population.
One category of evolutionary algorithm that has received recent attention is the “genetic algorithm.” Genetic algorithms adhere even more closely to the natural selection analogy than the description of evolutionary algorithms set forth above. As with other types of evolutionary algorithms, genetic algorithms typically maintain a population of solutions. Initially, the solution pool typically comprises one or more random initial guess solutions. However, the representation of these solutions is limited, such that the solutions (i.e., “genomes”) contained within the solution pool are defined using sequences of bits (i.e., “genes”). In each phase of the algorithm, a new generation of solutions is formed from the previous generation. First, one or more solutions in the solution pool are mutated, by complementing one or more bits in the bit sequence of that solution. Next, a pair of candidate solutions are selected to combine (referred to as “crossover”) to produce offspring. These solutions are then combined by concatenating subsequences from the parents' genomes. The solutions are then evaluated using objective criteria to determine the survivors, which survivors constitute a new population.
However, genetic algorithms also suffer from several drawbacks. First, in the context of MIP problems, with the use of genetic algorithms, it is quite difficult to pass desirable solution properties from parents to offspring using the representation described above. Further, in the same context, genetic algorithms are generally unable to retain linear feasibility in the offspring.
One example of an application of a genetic algorithm is disclosed in Kimmo Nieminen, Sampo Ruuth, and Istvan Maros, Genetic algorithm for finding a good first integer solution for milp, Technical Report 2003/4, Imperial College, 2003. In the system disclosed therein, an initial population of genomes is randomly generated. These solutions are then mutated by flipping a bit in the solution representation. However, the approach disclosed therein places little, if any emphasis on retaining feasibility in offspring. Moreover, this scheme is focused upon finding an initial feasible solution, and is not readily adaptable to improving known solutions.
Thus, even given the recent developments in methods for generating solutions to MIP models described above, current known solution techniques can leave significant optimality gaps for many important models due to non-optimal use of resources (such as time), limited applicability, and other concerns. Therefore, it would be desirable to provide an improved method for generating high quality solutions to difficult MIP models.
It would also be desirable to provide a method by which solutions to a MIP model might be improved given one or more resource limitations.
It would also be desirable to provide a method for implementing a domain independent evolutionary algorithm by which improved solutions to MIP models can be generated.
It would also be desirable to provide a method for implementing an evolutionary algorithm that uses sub-optimal solutions for improving the diversity in the solution pool.
It further would be desirable to provide a method for implementing an evolutionary algorithm wherein desirable solution properties are passed from parents to offspring.